565. Array Nesting

https://leetcode.com/problems/array-nesting/

題目介紹:

你會得到一個長度是n，範圍是[0 ~ n-1]的 nums
並且要組合一個集合 s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... }
詳細規則我們以Example 1 解釋

Example 1:

一開始的集合是 s[0] ，我們第一個元素就是 nums[0] = 5 ，第二個元素則是 nums[5] = 6 ，以此類推直到 nums[i] 等於 0。

而我們的任務是回傳最長的 s[k] 的長度

解法1:

這題的難度是Medium，不過其實蠻簡單的，很快就能想到硬幹的方法

只要照字面意思run過每個集合，並回傳最大的長度就好

但是，這種解法遇到長度很長的測試案例就會超過時間了，送出去會顯示 Time Limit Exceeded。

程式碼:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
    
        res = 0
        
        for i in range(len(nums)):
            count = 1
            j = nums[i]
            while nums[j] != nums[i]:
                j = nums[j]
                count += 1
            
            res = max(count, res) #紀錄最大的長度
            
        return res

解法修改:

上一個解法是因為我們會重複計算好幾個過程

像是 example1 中的 s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

我們可以知道 k = 0 時集合為長度4的 {5,6,2,0}

那我們就可以知道 k 為 5, 6, 2, 0時，就都是長度為4的集合，就像下圖繞圈圈的這種感覺

那我們就沒必要重複run過 k=5, k=6, k=2 了

程式碼:

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        
        res = 0
        visted = set()
        
        for i in range(len(nums)):
            
            if nums[i] in visted:
                continue
            
            count = 1
            j = nums[i]
            while nums[j] != nums[i]:
                visted.add(j) #記錄可以省略的數字
                j = nums[j]
                count += 1
            
            res = max(count, res)
            
        return res

閒聊:

今天是第一天，剛好遇到簡單好講解的題目

LeetCode題目雖然都有區分難度 easy medium hard

但是我覺得有時候 medium 的題目比一些 easy 題目簡單，有時候 easy 題目要多想一下

個人認為比較準確區分題目難易度的分法是看題目左上角的正讚倒讚比例

感覺倒讚比較多的題目就有點麻煩，像是今天這題的正讚比就超過9成